package 系统复习.面试题.数组_字符串;

import java.util.HashSet;
import java.util.Set;

/**
 * 对于任何字符串，我们可以通过删除其中一些字符（也可能不删除）来构造该字符串的 子序列 。(例如，“ace” 是 “abcde” 的子序列，而 “aec” 不是)。
 * 给定源字符串 source 和目标字符串 target，返回 源字符串 source 中能通过串联形成目标字符串 target 的 子序列 的最小数量 。
 * 如果无法通过串联源字符串中的子序列来构造目标字符串，则返回 -1。
 *
 * 滑动窗口
 */
public class L1055 {

    public int shortestWay(String source, String target) {

        int index = 0;
        int count = 0;
        Set<Character> characterList = new HashSet<>();
        for (int i = 0; i < source.length(); i++) {
            characterList.add(source.charAt(i));
        }
        for (int i = 0; i < target.length(); ) {

            if (target.charAt(i) == source.charAt(index)) {
                i++;
            } else {
                if (!characterList.contains(target.charAt(i))) {
                    return -1;
                }
            }
            if (index == source.length() - 1) {
                count++;
                index = 0;
            } else {
                index++;
            }

        }
        if (index != 0) count++;
        return count;
    }

    // 滑动窗口的概念
    // 以滑动窗口的方式扫target字符串找source的子序列，窗口大小为source的长度，每次向右移动的距离是source子序列的长度
    public int shortestWay1(String source, String target) {
        int n = source.length();
        int j = 0 ;
        int count = 0 ;
        while( j < target.length() ){
            int prev = j ;
            for(int i = 0 ; i < n ; i++){
                if( j < target.length() && source.charAt(i) == target.charAt(j) )
                    j++;
            }
            if( prev == j ) //如果j没有移动
                return -1;

            count++;
        }

        return count ;
    }

    public static void main(String[] args) {

        L1055 l1055 = new L1055();
        System.out.println(l1055.shortestWay("aaaaa", "aaaaaaaaaaaaa"));
        System.out.println(l1055.shortestWay("xyz", "xzyxz"));
    }
}
